#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1005;
long long f[maxn];
int n,m,w[maxn],v[maxn];

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=w[i];j<=n;j++){
			f[j]=max(f[j],f[j-w[i]]+v[i]);
		}
	}
	cout<<f[n]<<endl;
	return 0;
}